'''
Given n pairs of parentheses, write a function to generate all combinations of well-formed parentheses.

For example, given n = 3, a solution set is:

"((()))", "(()())", "(())()", "()(())", "()()()" 
'''

class Solution:
    # @param {integer} n
    # @return {string[]}
    def generateParenthesis(self, n):
        ss1 = ['(']
        ss2 = []
        for i in range(1, n*2):
            ss2 = []
            for j in range(0, len(ss1)):
                l = ss1[j].count('(')
                r = ss1[j].count(')')
                if l < n:
                    ss2.append(ss1[j]+'(')
                if r < l:
                    ss2.append(ss1[j]+')')
            ss1 = ss2

        return ss1

if __name__ == '__main__':
    print Solution().generateParenthesis(3)

